package algocasts;

public class P28_getIntersectionNode {
    class ListNode {
        int val;
        ListNode next;
    }

    public ListNode getIntersectionNode_withLen(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        for (ListNode p = headA; p != null; p = p.next) lenA++;
        for (ListNode p = headB; p != null; p = p.next) lenB++;
        ListNode p = headA, q = headB;
        if (lenA > lenB)
            for (int i = 0; i < lenA - lenB; i++) p = p.next;
        else
            for (int j = 0; j < lenB - lenA; j++) q = q.next;
        while (p != q) {
            p = p.next;
            q = q.next;
        }
        return q;
    }

    public ListNode getIntersectionNode_withoutLen(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode p = headA, q = headB;
        while (p != q) {
            p = p == null ? headB : p.next;
            q = q == null ? headA : q.next;
        }
        return q;
    }
}
